// https://www.lintcode.com/problem/median/description

class Solution {
public:
    /**
     * @param nums: A list of integers
     * @return: An integer denotes the middle number of the array
     */
    int median(vector<int> &nums) {
        priority_queue<int> q;
        int n = nums.size();
        int k = (n + 1) / 2;
        for (int i = 0; i < n; ++i)
        {
            if (q.size() == k)
            {
                if (nums[i] < q.top())
                {
                    q.pop();
                    q.push(nums[i]);
                }
            }
            else
            {
                q.push(nums[i]);
            }
        }
        return q.top();
    }
};